package code.递归;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * author : yeswater
 * date : 2023/12/6
 * <p>
 * 括号生成
 * <p>
 * 所有可能并且有效的括号组合
 */

public class T022 {
    public static void main(String[] args) {
        int n = 1;
        System.out.println(generateParenthesis(n));
    }

    private static List<String> res = new ArrayList<>();
    private static String[] arr = {"(", ")"};

    public static List<String> generateParenthesis(int n) { // n:( , )出现的次数
        if (n == 0) {
            return res;
        }
        generateParenthesis1("", n, n);
        return res;
    }

    /**
     * ❎ 错误思路:
     */
    public static void generateParenthesis1(String tmp, int l, int r) {
        if (l < 0 || r < 0) {
            res.add(tmp);
            return;
        }

        for (String s : arr) {
            if (s == "(" ) {
                generateParenthesis1(tmp + s, l-1, r);
            } else if (s == ")" ) {
                generateParenthesis1(tmp + s, l, r-1);
            }

        }
    }


    /**
     * 思路: https://leetcode.cn/problems/generate-parentheses/solutions/35947/hui-su-suan-fa-by-liweiwei1419/
     */
    public static void generateParenthesis(String tmp, int l, int r) {
        if (l == 0 && r == 0) {
            res.add(tmp);
            return;
        }

        // 因为先左后右,所以右大于左
        if (l > r) {
            return;
        }

        // 先左后右
        if (l > 0) {
            generateParenthesis(tmp + "(", l - 1, r);
        }

        if (r > 0) {
            generateParenthesis(tmp + ")", l, r - 1);
        }
    }
}
